package 动态规划;

import java.util.Arrays;

public class 超级丑数 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        //n指针法
        int len = primes.length;
        int[] idx = new int[len];
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=1;
        for (int i=1;i<n;i++){
            for (int j=0;j<len;j++){
                dp[i] = Math.min(dp[i],dp[idx[j]]*primes[j]);
            }
            for (int j=0;j<len;j++){
                if (dp[i]==dp[idx[j]]*primes[j])
                    idx[j]++;
            }
        }
        return dp[n-1];
    }
}
